class Solution {
public:
    int getMoneyAmount(int n) {
        return dfs(1, n);
    }
 
    int dfs(int left, int right)
    {
        if(left >= right)
            return 0;
        int ret = INT_MAX;
        for(int i = left; i <= right; ++i)
        {
            ret = min(ret, max(dfs(left, i - 1), dfs(i + 1, right)) + i);
        }
        return ret;
    }
};